package algorithms;

import java.util.Stack;

public class Problem85 {
	
	public static void main(String[] args){
		Problem85 p = new Problem85();
		char[][] matrix = {{'1'}};
		System.out.println(p.maximalRectangle(matrix));
	}
	
	public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if(m == 0)
        	return 0;
        int n = matrix[0].length;
        int[][] height = new int[m+1][n+1];
        int max = 0;
        for(int i = 1; i <= m; i++){
        	for(int j = 1; j <= n; j++){
        		if(matrix[i-1][j-1] == '1'){
        			height[i][j] = height[i-1][j] + 1;
        		}
        		if(j == n){
        			max = Math.max(max, largestRectangleArea(height[i]));
        		}
        	}
        }
        return max;
    }
	
	public int largestRectangleArea(int[] height) {
		if(height == null || height.length == 0)
			return 0;
		Stack<Integer> stack = new Stack<Integer>();
		int i = 0, max = Integer.MIN_VALUE;
		int len = height.length;
		while(i <= len){
			int h = (i == len ? 0 : height[i]);
			if(stack.isEmpty() || h >= height[stack.peek()]){
				stack.push(i);
				i++;
			} else{
				int high = height[stack.pop()];
				int width = stack.isEmpty() ? i : i - 1 - stack.peek();
				max = Math.max(max, high*width);
			}
		}
		return max;
	}
}
